use std::borrow::Borrow;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

pub struct Solution;

impl Solution {
  pub fn merge_two_lists(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    match (l1, l2) {
      (Some(mut n1), Some(mut n2)) => {
        if &n1.val <= &n2.val {
          let next = n1.next;
          n1.next = Solution::merge_two_lists(next, Some(n2));
          return Some(n1);
        } else {
          let next = n2.next;
          n2.next = Solution::merge_two_lists(Some(n1), next);
          return Some(n2);
        }
      }
      (Some(n1), None) => {
        return Some(n1);
      }
      (None, Some(n2)) => {
        return Some(n2);
      }
      (None, None) => {
        return None;
      },
    }
  }
}